Bit-reversal permutation

In applied mathematics, a bit-reversal permutation is a permutation of a sequence with n = 2m (a power of two) elements, defined by reversing the binary digits of the index (0 to n − 1) of each element. The generalization to n = bm for an arbitrary integer b > 1 is a base-b digit-reversal permutation, in which the base-b (radix-b) digits of the index of each element are reversed to obtain the permuted index. A further generalization to arbitrary composite sizes is a mixed-radix digit reversal (in which the elements of the sequence are indexed by a number expressed in a mixed radix, whose digits are reversed by the permutation).

Bit reversal is most important for radix-2 Cooley–Tukey FFT algorithms, where the recursive stages of the algorithm, operating in-place, imply a bit reversal of the inputs or outputs. Similarly, mixed-radix digit reversals arise in mixed-radix Cooley–Tukey FFTs. Mainly because of the importance of fast Fourier transform (FFT) algorithms, numerous efficient O(n) in-place algorithms for bit-reversal and digit-reversal permutations have been devised.[1][2][3][4][5][6]

References

  1. ^ B. Gold and C. M. Rader, Digital Processing of Signals (New York: McGraw–Hill, 1969).
  2. ^ Jeffrey J. Rodríguez, "An improved FFT digit-reversal algorithm," IEEE Trans. Acoustics, Speech, and Signal Processing, vol. 37 (no. 8), pp. 1298–1300 (1989)
  3. ^ David M. W. Evans, "A second improved digit-reversal permutation algorithm for fast transforms," IEEE Trans. Acoustics, Speech, and Signal Processing, vol. 37 (no. 8), pp. 1288–1291 (1989)
  4. ^ Karp, Alan H., "Bit reversal on uniprocessors," SIAM Review 38 (1), 1–26 (1996)
  5. ^ Carter, Larry and Kang Su Gatlin, "Towards an optimal bit-reversal permutation program," Proc. 39th Ann. Symp. on Found. of Comp. Sci. (FOCS), 544–553 (1998).
  6. ^ Rubio, M., P. Gómez, and K. Drouiche, "A new superfast bit reversal algorithm," Intl. J. Adaptive Control and Signal Processing 16, 703–707 (2002)